#include "heap.hpp" // 假设这是堆类的声明文件
#include <iostream>
#include <cstring> // 用于C风格的字符串操作，但在此例中未使用
#include <cassert> // 用于断言，但在此例中未使用
#include <algorithm> // 用于算法操作，但在此例中未使用到算法库的具体功能
#include <iterator> // 用于迭代器，但在此例中未使用

using namespace std;

// 堆类的构造函数
Heap::Heap(int capacity)
    :_a(new int[capacity]) // 动态分配一个整数数组作为堆的存储空间
    ,_capacity(capacity) // 堆的最大容量
    ,_size(0) // 当前堆中的元素数量
{}

// 堆类的析构函数
Heap::~Heap()
{
    delete[] _a; // 释放动态分配的存储空间
}

// 向堆中插入元素
void Heap::Push(HPDataType x) // HPDataType 应该是之前定义的堆中存储的数据类型，这里假设为 int
{
    if (_size >= _capacity) // 如果当前堆已满
    {
        // 扩容操作
        HPDataType* temp = new int[_capacity = 2 * _capacity]; // 分配新的存储空间，并将容量翻倍
        if (temp == nullptr) // 如果内存分配失败
        {
            cout << "内存分配失败" << endl;
            exit(-1); // 退出程序
        }
        for (int i = 0; i < _size; ++i) // 将原堆中的数据复制到新堆中
        {
            temp[i] = _a[i];
        }
        delete[] _a; // 释放原堆的存储空间
        _a = temp; // 更新堆的存储地址
    }
    _a[_size++] = x; // 将新元素添加到堆的末尾，并更新堆的大小
    AdjustUp(); // 调用AdjustUp函数，将新插入的元素上浮到正确的位置以维护堆的性质
}

// 上浮调整函数，用于维护最大堆的性质
void Heap::AdjustUp()
{   
    int child = _size - 1; // 新插入的元素的位置
    int parent = (child - 1) / 2; // 新插入元素的父节点的位置
    while (parent >= 0) // 当父节点存在时
    {
      if (_a[parent] < _a[child]) // 如果父节点的值小于子节点的值
      {
        swap(_a[parent], _a[child]); // 交换父节点和子节点的值
        child = parent; // 更新子节点的位置为父节点的位置
        parent = (parent - 1) / 2; // 更新父节点的位置为新的父节点的位置
      }
      else
        break; // 如果父节点的值不小于子节点的值，则跳出循环
    }
}

// 下沉调整函数，用于维护最大堆的性质（在Pop函数中调用）
void Heap::AdjustDown()
{
    int parent = 0; // 从根节点开始
    int child = parent * 2 + 1; // 左子节点的位置
    while (child < _size) // 当左子节点存在时
    {
      // 如果右子节点存在且右子节点的值大于左子节点的值，则更新child为右子节点的位置
      if (child < _size - 1 && _a[child] < _a[child + 1])
      {
        child += 1;
      }
      // 如果父节点的值小于子节点的值（无论是左子节点还是右子节点）
      if (_a[parent] < _a[child])
      {
        swap(_a[parent], _a[child]); // 交换父节点和子节点的值
        parent = child; // 更新父节点的位置为子节点的位置
        child = child * 2 + 1; // 更新子节点的位置为新的子节点的位置
      }
      else
        break; // 如果父节点的值不小于子节点的值，则跳出循环
    }
}

// 从堆中移除并返回堆顶元素
void Heap::Pop()
{
   if (!Empty()) // 如果堆不为空
   {
        swap(_a[_size - 1], _a[0]); // 将堆顶元素与堆的最后一个元素交换
        --_size; // 更新堆的大小
        AdjustDown(); // 调用AdjustDown函数，将新的堆顶元素下沉到正确的位置以维护堆的性质
   }
   else
   {
    cerr << "堆中无数据无法pop" << endl; // 如果堆为空，则输出错误信息
    exit(-2); // 退出程序
   }
}

// 判断堆是否为空
bool Heap::Empty()
{
  if (_size) return false; // 如果堆的大小不为0，则堆不为空
  else  return true; // 否则，堆为空
}

// 返回堆的大小
int Heap::Size()
{    
    return _size; // 返回堆的大小
}

// 返回堆顶元素
HPDataType Heap::Top()
{   
    if (!Empty()) // 如果堆不为空
    return _a[0]; // 返回堆顶元素（即根节点的值）
    else
    return -1; // 如果堆为空，则返回-1（这里可能需要根据实际情况调整返回值）
}